#include "Tree.h"
#include <iostream>
#include <bitset>
#include <string>

using namespace Huffman;
using namespace std;

Node* Tree::NYT = new Node(); /* Not Yet Transmitted */
Node* Tree::EOC = new Node(); /* End Of Coding */

Tree::Tree(void)
{
	setRoot(NYT);  
	nodeMap.insert(std::pair<char, Node*>((char)1, NYT)); 

	Node* top = new Node();
	NYT -> setParent(top);
	EOC -> setParent(top);
	top -> setLeft(NYT);
	top -> setRight(EOC);
	NYT -> setNext(EOC);
	EOC -> setPrev(NYT);	
	EOC -> setNext(top);
	
	EOC -> setParity(1);
	NYT -> setParity(0);	
	EOC -> setWeight(1);

	setRoot(top);  	
	nodeMap.insert(std::pair<char, Node*>((char)2, EOC)); //jakis char 

}

Tree::~Tree(void)
{
	// empty destructor
}

void Tree::setRoot(Node* n)
{
	this -> root = n;
}
		
Node* Tree::getRoot() const 
{
	return root;
}

void Tree::updateTreeVitter(char symbol){	

	Node* leafToIncrement = NULL;
	Node* p = findNode(symbol);	
	Node* symbolNode;
	if ( p == NULL ){ /* a new symbol */

		// creates a node for storing the newly added symbol
	     symbolNode = new Node();

		// creates new node for the both the symbol	and new escape node
		Node* top = new Node();		
		top -> setParent(NYT -> getParent());
		top -> setLeft(NYT);
		top -> setRight(symbolNode);
		top -> setWeight(0); //NYT -> getWeight() is the same as 0, by default
		top -> setParity(0); //NYT -> getParity() is the same as 0, by deafult 		

	    top -> setNext(NYT -> getNext());
		top -> setPrev(symbolNode);

		symbolNode -> setParent(top);
		symbolNode -> setSymbol(symbol);
		symbolNode -> setWeight(0);
		symbolNode -> setParity(1);

	    symbolNode -> setPrev(NYT);
	    symbolNode -> setNext(top); 
		
		NYT -> setNext(symbolNode);	
		NYT -> setParent(top);

		if ( getRoot() == NYT ){ //to bedzie tylko raz na poczatku, pozniej root juz nie bedzie sie zmienial
			setRoot(top);
		}

		p = symbolNode -> getParent();
		leafToIncrement = p -> getRight();		

	} else { /* swap p in tree with leader of its block */						

		/* Note that two node are in same block if have same  equal weights and ( both are leafs or both are internal nodes ) */
		slideHigherThanLeafNodesWithWeight(p,p -> getWeight() );
		
		/* if p is the sibling of NYT node */
		if ( NYT -> getNext() == p ){			
			leafToIncrement = p;
			p = p -> getParent();
		}
	}
	
	while ( p != getRoot() ){
		/* if possible advance p to the next block */	
		p = slideAndIncrement(p);
	}

	if ( leafToIncrement != NULL ){		
		slideAndIncrement( leafToIncrement );
	}

	// adds the node to the map
	nodeMap.insert(std::pair<char, Node*>(symbol, symbolNode)); 	
}

Node* Tree::slideAndIncrement(Node *p){	
	Node* fp = p -> getParent();
	int wt = p ->getWeight();
	
	if ( ! p -> isLeaf() ){ 		
		slideHigherThanLeafNodesWithWeight(p,wt+1);		
	} else {		
		slideHigherThanNodesWithWeight(p,wt);		
	}
	
	p -> setWeight(p -> getWeight() + 1);

	if ( ! p -> isLeaf() ){ 		
		p = fp;
	} else {		
		p = p -> getParent(); // p = new parent of p
	}

	return p;
}





Node* Tree::slideHigherThanLeafNodesWithWeight(Node* p, int weight){	
	Node* nextNodeInBlock = NULL;
	Node* nextNode = p -> getNext();
	 			
	while ( nextNode && nextNode -> isLeaf() && nextNode -> getWeight() <= weight  ){ // root is not leaf
		nextNodeInBlock = nextNode; 
		nextNode = nextNodeInBlock -> getNext();
	}

	if ( nextNodeInBlock && p-> getParent() != nextNodeInBlock ){
		swapNodes(p,nextNodeInBlock);
	}

	return p;

}

Node* Tree::slideHigherThanNodesWithWeight(Node* p, int weight){
	Node* nextNodeInBlock = NULL;
	Node* nextNode = p -> getNext();
	 			
	while ( nextNode && nextNode -> getWeight() <= weight  && nextNode != getRoot() ){
		nextNodeInBlock = nextNode;
		nextNode = nextNodeInBlock -> getNext();
	}

	if ( nextNodeInBlock && p-> getParent() != nextNodeInBlock ){ //dodatkowy bufor bezpieczenstwa
		swapNodes(p,nextNodeInBlock);
	}

	return p;
}

void Tree::swapNodes(Node* node, Node* nextNode){	
	Node* tmpNext = node -> getNext();	
	Node* tmpPrev = node -> getPrev();	
	Node* tmpParent = node -> getParent();	
	int tmpParity = node -> getParity();	
	
	if ( node -> getNext() == nextNode ) {
		
		node -> setNext(nextNode -> getNext() );
		nextNode -> getNext() -> setPrev(node);

		node -> setPrev(nextNode);					
		tmpPrev -> setNext(nextNode);		
		
		nextNode -> setNext(node);
		nextNode -> setPrev(tmpPrev);				

	} else {

		node -> setNext( nextNode -> getNext() );
		node -> setPrev( nextNode -> getPrev() );

		nextNode -> getNext() -> setPrev(node);
		nextNode -> getPrev() -> setNext(node);

		nextNode -> setNext(tmpNext);
		nextNode -> setPrev(tmpPrev);

		tmpNext->setPrev(nextNode);
		tmpPrev->setNext(nextNode);	

	}

	/* swap parities and  parent left,right  */
	if ( node -> getParity() ){
		node -> getParent() -> setRight(nextNode);
	} else {
		node -> getParent() -> setLeft(nextNode);
	}

	if ( nextNode -> getParity() ){
		nextNode -> getParent() -> setRight(node);
	} else {
		nextNode -> getParent() -> setLeft(node);
	}

	node -> setParity( nextNode -> getParity() );
	nextNode  -> setParity(tmpParity);

	/* swap parents */
	node -> setParent( nextNode -> getParent() );
	nextNode -> setParent(tmpParent);
}


Node* Tree::findNode(char symbol) 
{
	std::map<char,Node*>::iterator it;

	it = nodeMap.find(symbol);

	// returns the found node or NULL
	return it != nodeMap.end() ? it->second : NULL; //was NYT(ESC)
}